package com.xinpan.exercise;

public class Sqrt {
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(x < 2)
            return x;
        
        long s = 0;
        long e = x;
        long m = 0;
        long r = 0;
        
        while(s <= e)
        {
            m = (s+e)/2;
            r = m*m;
            if(r > x)
                e = m-1;
            else if(r < x)
                s = m+1;
            else
                return (int)m;
        }
        if(m*m > x)
            return (int)m-1;
        else
            return (int)m;

    }
}
